package Yesterday;

public class Solution2 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        /*
        利用中序遍历 和 后序遍历 -- 以 后序遍历 来创建，中序遍历分出左右子树
        postIndex 来记录后序数组进行的下标
         */
        postIndex = postorder.length - 1;
        return buildTreeChild(postorder,inorder,0, postorder.length-1);
    }
    //后续遍历 左右根 反过来 根右左
    public TreeNode buildTreeChild(int[] postorder, int[] inorder, int being, int end) {
        if(being > end) {
            return null;
        }
        //需要找到在中序数组中 后续数组的位置 分清左右子树
        TreeNode root = new TreeNode(postorder[postIndex]);
        int inIndex = findIndex(inorder,being,end,postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(postorder,inorder,inIndex+1,end);
        root.left = buildTreeChild(postorder,inorder,being,inIndex -1 );
        return root;
    }
    public int findIndex(int[] inorder, int begin, int end, int key) {
        for (int i = begin; i <= end ; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
